In [21]:

    

import networkx as nx
from random import random
import math, time


    

In [22]:

    

import json
from networkx.readwrite import json_graph


    

In [23]:

    

import vincent
from IPython.display import display
vincent.initialize_notebook()


    

In [24]:

    

import matplotlib.pyplot as plt
%matplotlib inline
%config InlineBackend.figure_format = 'svg'


    

In [25]:

    

%load_ext autoreload
%autoreload 2


    

    




The autoreload extension is already loaded. To reload it, use:
  %reload_ext autoreload

In [26]:

    

from randomwalk import plotrwtraversal, randomwalk, edgetokey


    

In [27]:

    

def rungraph(G, k=2):
    # Convert to DiGraph if necessary
    if G.is_multigraph():
        if G.is_directed():
            Gm = G.copy()
            G = nx.DiGraph()
            G.graph['name'] = Gm.graph['name']
            for (u,v) in Gm.edges_iter():
                G.add_edge(u,v)

    # Randomize the expensive edges
    expensiveedges = []
    for e in G.edges_iter():
        if random() > 1/float(k):
            expensiveedges.append(edgetokey(e))
            G.edge[e[0]][e[1]]['expensive'] = True
        else:
            G.edge[e[0]][e[1]]['expensive'] = False

    get_ipython().run_cell_magic(u'html', u'', '<h2>Graph: '+G.graph['name']+'</h2>')
        
    if False:
        # Save and plot graph
        d = json_graph.node_link_data(G)
        for node in d['nodes']:
            node['name']=node['id']
            node['value']=G.degree(node['id'])

        d['adjacency'] = json_graph.adjacency_data(G)['adjacency']
        json.dump(d, open('graph.json','w'))

        time.sleep(1)

        get_ipython().run_cell_magic(u'html', u'', u'<div id="d3-example"></div>\n<style>\n.node {stroke: #fff; stroke-width: 1.5px;}\nmarker {stroke: #999;}\n.link {stroke: #999; stroke-opacity: .6;}\n</style>\n<script src="force.js"></script>')
        #nx.draw_graphviz(G)

    # Run algos
    G1 = G.copy()
    randomwalk(G1, frogs, P_die)
    G2 = G.copy()
    randomwalk(G2, frogs, P_die, 4, expensiveedges)

    # Make graphs
    (line1, df1) = plotrwtraversal(G1,expensiveedges, time=G2.graph['endtime']+1)
    (line2, df2) = plotrwtraversal(G2, expensiveedges)
    get_ipython().run_cell_magic(u'html', u'', '<h3>'+"Vanilla random walk. Cost: " + str(G1.graph['cost'])+'</h3>')
    display(line1)

    get_ipython().run_cell_magic(u'html', u'', '<h3>'+"Waiting random walk. Cost: " + str(G2.graph['cost'])
                                 + ', a ' + str( 100*(1 - G2.graph['cost'] / float(G1.graph['cost']) ) ) + '% gain</h3>')
    display(line2)

    (l, d) = plotrwtraversal(G2, countfrogs=True, expensiveedges = expensiveedges)
    get_ipython().run_cell_magic(u'html', u'', '<h4>'+"Waiting algorithm: What are the frogs up to?"+'</h4>')
    display(l)

    get_ipython().run_cell_magic(u'html', u'', '<h3>'+'Performance stats'+'</h3>')
    print "Stats normalized by equivalent vanilla random walk stats:"
    print
    print "Average death round (waiting/vanilla):", G2.graph['death_times_sum'] / float(L*frogs)
    print "Total duration in rounds (waiting/vanilla):", G2.graph['endtime'] / float(G1.graph['endtime'])
    print "Cost (waiting/vanilla):", G2.graph['cost'] / float(G1.graph['cost'])


    

In [28]:

    

G = nx.read_edgelist('datasets/livejournal/supersmall-soc-LiveJournal1.txt', 
                     nodetype = int
                     )


    

In [29]:

    

G.graph['name'] = '1% of LiveJournal'


    

In [30]:

    

frogs = 1000
# Life expectancy L. L should be the mean of a geometric distribution
L = 6
# P_die is the probability that a frog dies at any given time
P_die = 1/float(L)


    

In [ ]:

    

rungraph(G, k=4)


    

    





Graph: 1% of LiveJournal

In [ ]: